1. Field of the Invention
The present invention relates to mesh networks and, more particularly, to a method and apparatus for cycle-based restoration in mesh networks.
2. Description of the Related Art
Data communication networks may include various computers, servers, nodes, routers, switches, hubs, proxies, and other devices coupled to and configured to pass data to one another. These devices will be referred to herein as “network devices.” Data is communicated through the data communication network by passing data packets (or cells, frames, or segments) between the network devices by utilizing one or more communication links. A particular packet may be handled by multiple network devices and cross multiple communication links as it travels between its source and its destination over the network. A subset of data packets destined to travel between the same end points on a network are referred to as a flow. Multiple flows may be carried by a single communication link.
Communications networks may experience local failure on a link for many reasons. To mitigate against the effect of such failures, it is desirable to be able to restore flows in the network with minimum delays, especially where the flows are associated with traffic of high importance or with revenue producing traffic. One way to restore the flows in the network is to cause the flows to be diverted around the failed area over one or more restoration paths until the area can be repaired.
Restoration paths may be created after a failure is detected utilizing a protocol exchange between network devices involved in handling traffic over the affected link. Unfortunately, protocol exchanges are time consuming. For example, it may take up to 30 seconds to establish a new path through an IP network using an Open Shortest Path First (OSPF) protocol exchange.
Alternatively, restoration paths may be determined ahead-of-time, before a failure takes place, and pre-programmed into the network devices handling the traffic on the network. By pre-programming the restoration paths into the network, a network device that senses a link failure may simply use the alternative restoration path to restore traffic in real time. One example of a network protocol that includes alternate restoration paths is SONET. Specifically, in SONET there are two choices (east/west). If east isn't available, the west choice is utilized. SONET restoration is thus very fast, since there is no need to notify the source to redirect the traffic—it is done by the SONET switch itself.
Networks have evolved since SONET was developed, so that now switches residing in mesh networks are able to choose between many different paths to restore traffic over a failed link. For example, if two nodes A and B are connected by three links, it is possible to set the maximum bandwidth on each link to be 66% and reserve 33% on each link as back-up. In the event that one of the links fails, the 66% traffic from the failed link may be split and passed over the 33% backup capacity on each of the other two links to achieve total restoration over the links.
To designate portions of a mesh network to back up particular links in the mesh, logical restoration rings, referred to herein as p-cycles, are defined. Defining a p-cycle enables the network devices to perform fast link restoration protection without requiring notification of the source or destination nodes. Thus, in a mesh network the working path will be carried over the mesh network, while the restoration path will be carried over the logical ring. Restoration of traffic from a failed arc, however, should not have an unplanned negative impact on traffic which normally uses the restoration path.
Several methods have been developed to attempt to create restoration paths through a mesh network, one of which is to attempt to restore protection cycles (p-cycles). Unfortunately, this method tends to establish back-up paths with many hops (arcs) which results in a less than optimal restoration path. Additionally, p-cycles do not account for flows or bandwidths on the various links used to establish a back-up path. Hence, p-cycles may result in restoring flows across a bottleneck in the network, which either causes additional connectivity displacement in the network or results in an ineffectual restoration of traffic from the failed link.